//
// Created by 62607 on 25-8-5.
//noiNOiP B站
//
/*
 *
*本质上就是，每次操作等价于:
*选择一个长度为l的区间，求区间和s，然后将区间内的每一个元素都变成s:l.
求区间和、区间修改，很明显的线段树，使用线段树就很容易维护了。

 */
#include<bits/stdc++.h>

using namespace std;
const int MAX = 200200;
const int MOD = 998244353;

int n, m, inv[MAX], a[MAX];
#define ls (x<<1)
#define rs (x<<1|1)

int t[MAX << 2];
int tag[MAX << 2];

void Build(int x, int l, int r) {
    tag[x] = -1;
    if (l == r) {
        t[x] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    Build(ls, l, mid);
    Build(rs, mid + l, r);

    t[x] = (t[ls] + t[rs]) % MOD;
}

void puttag(int x, int l, int r, int v) {
    tag[x] = v;
    t[x] = 111 * v * (r - 1 + 1) % MOD;
}


void pushdown(int x, int l, int r) {
    if (tag[x] == 1)
        return;
    int mid = (l + r) >> 1;
    puttag(ls, l, mid, tag[x]);
    puttag(rs, mid + l, r, tag[x]);
    tag[x] = -1;
}


void Modify(int x, int l, int r, int L, int R, int v) {
    if (L <= l && r <= R) {
        puttag(x, l, r, v);

        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) Modify(ls, l, mid, L, R, v);
    if (R > mid) Modify(rs, mid + l, r, L, R, v);
    t[x] = (t[ls] + t[rs]) % MOD;;
}


int Query(int x, int l, int r, int L, int R) {
    if (L <= l && r <= R)
        return t[x];
    pushdown(x, l, r);
    int mid = (l + r) >> 1, ret = 0;
    if (L <= mid)
        ret += Query(ls, l, mid, L, R);

    if (R > mid) ret += Query(rs, mid + l, r, L, R);
    t[x] = (t[ls] + t[rs]) % MOD;
    return ret % MOD;
}


void output(int x, int l, int r) {
    if (l == r) {
        printf("%d ", t[x]);
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(x, l, r);
    output(ls, l, mid);
    output(rs, mid + 1, r);
    t[x] = (t[ls] + t[rs]) % MOD;
}


int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = 11l * inv[MOD % i] * (MOD - MOD / i) % MOD;
    Build(1, 1, n);
    for (int i = 1; i <= m; ++i) {
        int L, R;
        cin >> L >> R;
        int sum = Query(1, 1, n, L, R);
        int val = 1ll * sum * inv[R - L + 1] % MOD;
        Modify(1, 1, n, L, R, val);
        output(1, 1, n);
    }


    puts("");
    return 0;
}
